/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : sunzb(sunzb@hsit.com.cn)
 * @date: 2019/5/15
 */
// 1ms
public class _18_51_NQueens {
    private int n;
    private int[] cache;
    private boolean[] addCache;
    private boolean[] minusAddCache;

    // 撇 i + j，捺 i - j + n
    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        // init
        cache = new int[n];
        for (int i = 0; i < cache.length; i++)
            cache[i] = -1;
        addCache = new boolean[n << 1];
        minusAddCache = new boolean[n << 1];
        List<List<String>> result = new ArrayList<>();
        dfs(0, result);
        return result;
    }

    private void dfs(int row, List<List<String>> result) {
        if (row == n) addToResult(result);
        else {
            for (int col = 0; col < n; col++) {
                if (cache[col] == -1 && !addCache[col + row] &&
                        !minusAddCache[row - col + n]) {
                    cache[col] = row;
                    addCache[row + col] = true;
                    minusAddCache[row - col + n] = true;
                    dfs(row + 1, result);
                    cache[col] = -1;
                    addCache[row + col] = false;
                    minusAddCache[row - col + n] = false;
                }
            }
        }
    }

    private void addToResult(List<List<String>> result) {
        List<String> newSolution = new ArrayList<>();
        char[] temp = new char[n];
        for (int col = 0; col < n; col++) {
            int key = cache[col];
            for (int row = 0; row < n; row++)
                temp[row] = '.';
            temp[key] = 'Q';
            newSolution.add(new String(temp));
        }
        result.add(newSolution);
    }

    public static void myPrint(List<List<String>> result) {
        for (List<String> list : result) {
            for (String s : list) {
                System.out.println(s.replace('.', '+'));
            }
            System.out.println("-------------");
        }
    }

    public static void main(String[] args) {
        myPrint(new _18_51_NQueens().solveNQueens(8));
    }
}
